package com.pandai.leetcode.leetcode707;

public class MyLinkedList {
    static class ListNode{
        int val;
        ListNode next;
        public ListNode(){}
        public ListNode(int val,ListNode next){
            this.val = val;
            this.next = next;
        }

    }
    // cnt用来统计链表中的结点个数,head指的是广义上的头结点，并非链表的第一个结点
    int cnt;
    ListNode head;

    public MyLinkedList() {
        // 初始化链表结点个数为0，head为其头结点，头结点元素值为-1，头结点不计入链表中的结点个数
        this.cnt = 0;
        this.head = new ListNode(-1,null);
    }

    public int get(int index) {
        if( index < 0 || index > cnt - 1){
            return -1;
        }
        // head指的是广义上的头结点，并非链表的第一个结点,因此其不可能为null
        ListNode cur = head.next;
        for(int i=0;i<index;i++){
            cur = cur.next;
        }
        return cur.val;
    }

    public void addAtHead(int val) {
        ListNode cur = new ListNode(val,null);
        ListNode tmp = head.next;
        head.next = cur;
        cur.next = tmp;
        cnt++;
    }

    public void addAtTail(int val) {
        ListNode prev = head;
        ListNode cur = head.next;
        ListNode addNode = new ListNode(val,null);
        while(cur!=null){
            prev = prev.next;
            cur = cur.next;
        }
        prev.next = addNode;
        cnt++;
    }

    public void addAtIndex(int index, int val) {
        if( index < 0 || index > cnt){
            return;
        }
        if(index == cnt){
            // 相当于尾插
            addAtTail(val);
            return;
        }
        ListNode prev = head;
        ListNode cur = head.next;
        ListNode addNode = new ListNode(val,null);
        for(int i=0;i<index;i++){
            prev = prev.next;
            cur = cur.next;
        }
        prev.next = addNode;
        addNode.next = cur;
        cnt++;
    }

    public void deleteAtIndex(int index) {
        if( index < 0 || cnt < index + 1){
            return;
        }
        ListNode prev = head;
        ListNode cur = head.next;
        for(int i=0;i<index;i++){
            prev = prev.next;
            cur = cur.next;
        }
        prev.next = cur.next;
        cnt--;
    }


    public static void main(String[] args) {
        MyLinkedList myLinkedList = new MyLinkedList();
        myLinkedList.addAtHead(7);
        myLinkedList.addAtHead(2);
        myLinkedList.addAtHead(1);
        myLinkedList.addAtIndex(3, 0);
        myLinkedList.deleteAtIndex(2);
        myLinkedList.addAtHead(6);
        myLinkedList.addAtTail(4);
        myLinkedList.get(4);
        myLinkedList.addAtHead(4);
        myLinkedList.addAtIndex(5, 0);
        myLinkedList.addAtHead(6);
    }
}
